#include <bits/stdc++.h>
#define Del(a, b) memset(a, b, sizeof(a))
using namespace std;
int a[4000];      //随机生成的页
int c;            //用户页面容量
int MAXNUM = 600; //总页表数量

void init() //生成页
{
    srand(time(0));
    for (int i = 1; i <= MAXNUM; i++)
    {
        int q = rand() % 317;
        //a[i++]=q/10;
        a[i++] = (q + 1) / 10;
        int head = rand() % (q + 2);
        //a[i++]=head/10;
        a[i++] = (head + 1) / 10;
        int tail = (rand() % (318 - q)) + q + 3;
        a[i] = tail / 10;
        //a[i]=(tail+1)/10;
    }
    // c = (rand() % 29) + 4;
    c = 10;
}

struct node
{
    int dis, val, pos; //距离下一个相同元素的距离，元素，位置
    node() {}
    node(int dd, int vv, int pp)
    {
        dis = dd;
        val = vv;
        pos = pp;
    }
    bool operator<(const node &a) const //优先队列
    {
        if (a.dis != dis)
            return a.dis > dis;
        else
            return a.val > val;
    }
};

void OPT() //最佳淘汰法 （优先队列实现）
{

    int poss[400];
    int lack = 0;
    int head[400], net[400]; //领接表存储最近距离
    Del(head, -1);
    Del(poss, 0);

    priority_queue<node> q;
    for (int i = 1; i <= MAXNUM; i++)
    {
        net[i] = head[a[i]];
        head[a[i]] = i;
    }
    int t = 1, tt = 1;
    for (int i = 1; i <= MAXNUM; i++) //优先填满  c页
    {
        if (!poss[a[i]])
        {
            poss[a[i]] = t;
            t++;
        }
        q.push(node(net[i], a[i], poss[a[i]]));
        tt = i;
        if (t > c)
            break;
    }
    if (t <= c)
    {
        printf("100%% 命中率\n");
        return;
    }
    for (int i = tt + 1; i <= MAXNUM; i++)
    {
        if (!poss[a[i]])
        {
            lack++;
            node p = q.top();
            q.pop();
            poss[a[i]] = p.pos;
            poss[p.val] = 0;
        }
        q.push(node(net[i], a[i], poss[a[i]]));
    }
    printf("缺页数 %d\n", lack);
    printf("%lf%%命中率\n", (1.0 - ((1.0 * lack) / (1.0 * MAXNUM))) * 100.0);
}

void FIFO()
{
    int vis[400];
    Del(vis, 0);
    int lack = 0;
    int t = 0, tt = 0;
    queue<int> q;
    for (int i = 1; i <= MAXNUM; i++)
    {
        if (!vis[a[i]])
        {
            vis[a[i]] = 1;
            t++;
            q.push(a[i]);
        }
        tt = i;
        if (t > c)
            break;
    }

    if (t <= c)
    {
        printf("100%% 命中率\n");
        return;
    }

    for (int i = tt + 1; i < MAXNUM; i++)
    {
        if (!vis[a[i]])
        {
            vis[a[i]] = 1;
            vis[q.front()] = 0;
            q.pop();
            lack++;
            q.push(a[i]);
        }
    }
    printf("缺页数 %d\n", lack);
    printf("%lf%%命中率\n", (1.0 - ((1.0 * lack) / (1.0 * MAXNUM))) * 100.0);
}

void LRU()
{
	//int mytime = 0;
	int time[400] = { 0 };
	int vis[400] = { 0 };
	int lack = 0;
	int t = 0, tt = 0;
	int subscript = c+1;
	int maxtime = 0;
	queue<int>q;
	stack<int>s1,s2;
	for (int i = 1; i <= 320; i++)
	{
		//mytime++;
		if (!vis[a[i]])
		{
			vis[a[i]] = 1;
			s1.push(a[i]);
			t++;
		}
		//q.push(a[i]);
		// 内存页内时间++
		while (!s1.empty()) {
			time[s1.top()]++;
			s2.push(s1.top());
			s1.pop();
		}
		// 辅助栈读回内存栈
		while (!s2.empty()) {
			s1.push(s2.top());
			s2.pop();
		}
		//time[a[i]]++;
		tt = i;
		if (t > c)
			break;
	}
	if (t <= c)
	{
		printf("100%% 命中率\n");
		return;
	}
	for (int i = tt + 1; i < 320; i++)
	{
		//mytime++;
		if (!vis[a[i]])
		{
			// 寻找最大时间页
			while (time[s1.top()])
			{
				time[s1.top()]++;
				if (time[s1.top()] > maxtime) {
					subscript = s1.top();
					break;
				}
				s2.push(s1.top());
				s1.pop();
			}
			// 其他页归位
			while (!s2.empty()) {
				if (s2.top() != subscript) {
					s1.push(s2.top());
				}
				s2.pop();
			}
			vis[subscript] = 0;
			time[subscript] = 0;
			vis[a[i]] = 1;
			time[a[i]]++;
			s1.push(a[i]);
			lack++;
		}
		else {
			while (!s1.empty()) {
				time[s1.top()]++;
				if (s1.top() == a[i]) {
					time[s1.top()] = 1;
					s1.pop();
					break;
				}
				s2.push(s1.top());
				s1.pop();
			}
			while (!s2.empty()) {
				s1.push(s2.top());
				s2.pop();
			}
			s1.push(a[i]);
		}
		//q.push(a[i]);
		//time[a[i]]++;
	}
	printf("缺页数 %d\n", lack);
	printf("%lf%%命中率\n", (1.0 - ((1.0 * lack) / (1.0 * 320))) * 100.0);
}

void Clock()
{
    int sign[400] = {0};
    int vis[400] = {0};
    int lack = 0;
    int t = 0, tt = 0;
    int tmpint;
    queue<int> q;
    for (int i = 1; i <= MAXNUM; i++)
    {
        if (!vis[a[i]])
        {
            vis[a[i]] = 1;
            t++;
            q.push(a[i]);
            sign[a[i]] = 1;
        }
        tt = i;
        if (t > c)
            break;
    }
    if (t <= c)
    {
        printf("100%% 命中率\n");
        return;
    }
    for (int i = tt + 1; i < MAXNUM; i++)
    {
        if (!vis[a[i]])
        {
            while (true)
            {
                if (sign[q.front()] == 0)
                {
                    vis[q.front()] = 0;
                    q.pop();
                    break;
                }
                sign[q.front()] = 0;
                tmpint = q.front();
                q.pop();
                q.push(tmpint);
            }
            q.push(a[i]);
            vis[a[i]] = 1;
            sign[a[i]] = 1;
            lack++;
        }
        sign[a[i]] = 1;
    }
    printf("缺页数 %d\n", lack);
    printf("%lf%%命中率\n", (1.0 - ((1.0 * lack) / (1.0 * MAXNUM))) * 100.0);
}

void BetterClock()
{
    int sign[400] = {0};
    int M[400] = {0};
    int vis[400] = {0};
    int lack = 0;
    int t = 0, tt = 0;
    int tmpint;
    int endint;
    int flag;
    queue<int> q;
    for (int i = 1; i <= MAXNUM; i++)
    {
        if (!vis[a[i]])
        {
            vis[a[i]] = 1;
            t++;
            q.push(a[i]);
            sign[a[i]] = 1;
            M[a[i]] = rand() % 2;
        }
        tt = i;
        if (t > c)
            break;
    }
    if (t <= c)
    {
        printf("100%% 命中率\n");
        return;
    }
    for (int i = tt + 1; i < MAXNUM; i++)
    {
        if (!vis[a[i]])
        {
            endint = q.front();
            flag = 0;
            while (true)
            {
                if (endint == q.front() && flag != 0)
                {
                    break;
                }
                flag++;
                if (sign[q.front()] == 0 && M[q.front()] == 0)
                {
                    endint = -1;
                    vis[q.front()] = 0;
                    M[q.front()] = 0;
                    q.pop();
                    break;
                }
                tmpint = q.front();
                q.pop();
                q.push(tmpint);
            }

            if(endint == -1){
                q.push(a[i]);
                vis[a[i]] = 1;
                sign[a[i]] = 1;
                M[a[i]] = rand() % 2;
                lack++;
                continue;
            }

            flag = 0;
            while (true)
            {
                if (endint == q.front() && flag != 0)
                {
                    break;
                }
                flag++;
                if (sign[q.front()] == 0 && M[q.front()] == 1)
                {
                    endint = -1;
                    vis[q.front()] = 0;
                    M[q.front()] = 0;
                    q.pop();
                    break;
                }
                sign[q.front()] = 0;
                tmpint = q.front();
                q.pop();
                q.push(tmpint);
            }

            if(endint == -1){
                q.push(a[i]);
                vis[a[i]] = 1;
                sign[a[i]] = 1;
                M[a[i]] = rand() % 2;
                lack++;
                continue;
            }

            flag = 0;
            while (true)
            {
                if (endint == q.front() && flag != 0)
                {
                    break;
                }
                flag++;
                if (sign[q.front()] == 0 && M[q.front()] == 0)
                {
                    endint = -1;
                    vis[q.front()] = 0;
                    M[q.front()] = 0;
                    q.pop();
                    break;
                }
                tmpint = q.front();
                q.pop();
                q.push(tmpint);
            }

            if(endint == -1){
                q.push(a[i]);
                vis[a[i]] = 1;
                sign[a[i]] = 1;
                M[a[i]] = rand() % 2;
                lack++;
                continue;
            }

            flag = 0;
            while (true)
            {
                if (endint == q.front() && flag != 0)
                {
                    break;
                }
                flag++;
                if (sign[q.front()] == 0 && M[q.front()] == 1)
                {
                    endint = -1;
                    vis[q.front()] = 0;
                    M[q.front()] = 0;
                    q.pop();
                    break;
                }
                sign[q.front()] = 0;
                tmpint = q.front();
                q.pop();
                q.push(tmpint);
            }

            if(endint == -1){
                q.push(a[i]);
                vis[a[i]] = 1;
                sign[a[i]] = 1;
                M[a[i]] = rand() % 2;
                lack++;
                continue;
            }
        }
        sign[a[i]] = 1;
        M[a[i]] = rand() % 2;
    }
    printf("缺页数 %d\n", lack);
    printf("%lf%%命中率\n", (1.0 - ((1.0 * lack) / (1.0 * MAXNUM))) * 100.0);
}

int main()
{
    //printf("!!\n");
    init();
    printf("OPT:\n");
    OPT(); //优先队列
    printf("FIFO:\n");
    FIFO(); //队列
    printf("LRU:\n");
    LRU(); //队列
    printf("CLOCK:\n");
    Clock(); //队列
    printf("BetterCLOCK:\n");
    BetterClock(); //队列
}
